const common = require('./base/common');
const Dump = require('./dataStruct/dump').Dump;

/**
 * 480. 滑动窗口中位数
 * 
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var medianSlidingWindow = function(nums, k) {
    // 用大顶堆维护比中位数小的部分 - smallHalf
    // 用小顶堆维护比中位数大的部分 - largeHalf
    let smallHalf = new Dump(true), 
        largeHalf = new Dump(false);

    // 调整平衡
    function makeBalance() {
        if(smallHalf.length > largeHalf.length + 1) {
            largeHalf.add(smallHalf.poll());
        } else if(smallHalf.length < largeHalf.length) {
            smallHalf.add(largeHalf.poll());
        }
    }

    // 添加一个数字到我们维护的两个堆中
    function insert(num) {
        if(smallHalf.isEmpty() || num <= smallHalf.peek) {
            smallHalf.add(num);
        } else {
            largeHalf.add(num);
        }
        makeBalance();
    }

    // 移除一个数字
    function remove(num) {
        if(num <= smallHalf.peek) {
            smallHalf.remove(num);
        } else {
            largeHalf.remove(num);
        }
        makeBalance();
    }  

    // 计算中位数
    function calMedian() {
        return (k & 1) == 0? (smallHalf.peek + largeHalf.peek) / 2: smallHalf.peek;
    }

    // 先填充满双端队列
    for(let i=0; i < k; ++i) {
        insert(nums[i]);
    }

    // 然后再依次滑动窗口进行计算
    let results = [calMedian()];
    for(let i=k; i < nums.length; ++i) {
        remove(nums[i - k]);
        insert(nums[i]);
        results.push(calMedian());
    }

    return results;
};

common.testing([
    [[1,3,-1,-3,5,3,6,7], 3],
    [[670171779,25361138,42884260,141714653,824765604,621543621,923179139,302439598,8531137,648898857,914108711,120073717,237312017,625937240,752289674,141815960,941475197,507103461,318252662,638209204,494253441,450836291,883236221,144198283,971967143,736648250,603912795,954629843,613444564,93797901,208325209,923443053,443074902,434073765,268798074,176615008,546039302,84925083,52223304,543742352,927770657,955649910,577841457,860316065,324709204,631644601,39141886,520660598,539787639,239923745,217071727,897283083,799585325,470872927,484044894,674478622,543511088,188400256,52206914,61254200,293145996,577268554,968953579,627285630,585338865,960695726,631008736,882555644,236137457,5438721,7249251,17550834,564585977,59257924,663000107,543132644,624847958,417574854,996991360,766373626,627596054,714689161,697669834,269165996,65312768,933505315,701282801,69781671,87451813,716785121,417247555,145549430,58374655,495778484,312430228,417325081,301045265,196296523,620780269,978423957,89160220,365210512,584812058,51090134,264380494,92275593,185676995,172494452,804309892,774280626,376558940,191796871,157056750,395395087,90823391,400838098,229712447,748983070,402297354,133107922,259863458,690884255,40573034,951644917,630895741,337953748,687374899,395390280,803010720,59428223,230248106,14385648,261417472,684888720,412369120,758070971,25815593,676932013,620959263,839292468,108894758,124087618,919931645,201877693,81707638,456694942,565335816,131405184,706716950,852705671,265836066,933754080,587308862,65202022,426702362,931679379,77547507,965860067,174236974,26106088,678357028,155887673,74070771,514416584,823343044,689402887,913024822,83020470,608152387,135470814,111262234,112067457,967569958,202109022,320181778,848607111,893793428,131012209,544437066,718926973,262637189,857319516,146812620,20993937,657781051,80309401,140372291,93029009,756416403,780273559,522557531,209285865,36802916,657276032,975368234,271231287,269436606,525509166,425291429,47469987,904617050,507517168,35996692,553497637,528604833,121580592,148061447,328171434,839285742,202872298,263659628,68604035,622276384,353824998,354522843,345785523,319514857,22579030,528635338,427256705,511103945,189415615,937476451,79193918,719802333,735405758,989164799,14843944,960020912,819806651,28282783,547826472,850098793,194689038,166562216,239972271,32648209,903097256,734143174,450773403,619256183,132914319,300945131,453806610,58758704,862544155,57974413,4340709,732830743,867582056,37652062,458013816,49793242,942353120,436991215,117277765,844892056,731889806,878618004,835236456,865999200,144857259,955453471,571258478,534832587,712227014,118554498,473602048,255224954,833937397,153045988,705994857,601390502,157619263,259616490,480555304,6997961,650613589,668838377,237193841,580215433,750519982,817878643,836507032,745733562,622391220,929368581,249176236,104865380,181346051,603784064,938531573,632760196,461594228,303257032,655221071,797377059,218273333,410817233,238288504,650863651,931168186,75861344,543805937,848960105,591134067,930913047,437212534,334997482,748041187,751938949,689631826,672856723,54058359,173257032,90595139,652552606,45642391,252982136,646117270,615637658,238885338,91918101,265254823,109242636,528422223,140400194,207489661,558268277,458877796,745340995,673990014,921411020,443413201,470392695,795698836,722645361,126053473,161844769,56230412,171729804,44794260,237851370,893887101,557890673,554938309,326680442,549986962,654232224,357694706,761174367,290479568,652748323,40090716,642282301,231318016,816493842,391498164,19747940,191145942,747289860,216309364,614644955,941416615,877020856,554752362,496436507,427383132,488478887,34671328,752941359,711772589,70968111,346091001,365737731,648825781,685920379,571592757,65113868,92581731,681465998,868738935,153964592,112586756,898472241,310927361,928443176,728279930,691479257,303353413,334634313,86710745,792052058,915294700,725638017,31498984,915425504,776577198,320338898,194355657,212900112,504426482,777928265,552885497,977786088,105914172,628524019,131127740,545704358,897972216,496941774,536492435,692004939,548556199,436740022,190444308,46850526,83270611,517304880,122293682,834020351,547253866,816244339,493068537,10991233,632016545,640932331,164692343,670766396,429154469,194568788,647509182,32677456,601673007,610713504,437512715,85172255,58959461,380173269,808282258,965842931,886232222,105863209,564967456,382829605,149143401,332703136,487168542,634023030,4187374,303213045,122952984,591533674,204656955,193618769,712925378,325561433,715650453,28740371,441551978,253588792,459271496,712784532,898824936,943704932,327553960,198818459,850264259,35213875,74572778,800187154,202899764,725280690,675376458,601055211,964834367,322187672,201929217,593166437,522195863,573182730,17986315,86759134,812347403,569258242,276604487,382495832,188892953,536009383,808779494,732953795,581211951,319128832], 12]
], [[1,-1,-1,3,5,6], common.SKIP])(x => medianSlidingWindow(x[0], x[1]));